package cn.xiaolang.function.data_structure;

/**
 * 64. 最小路径和
 * 给定一个包含非负整数的 mxn 网格grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 * <p>
 * 示例 1：
 * 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
 * 输出：7
 * 解释：因为路径 1→3→1→1→1 的总和最小。
 * <p>
 * 示例 2：
 * 输入：grid = [[1,2,3],[4,5,6]]
 * 输出：12
 * <p>
 * 提示：
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 200
 * 0 <= grid[i][j] <= 100
 */
public class No17minPathSum {

    public static void main(String[] args) {
        int[][] grid = new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        No17minPathSum obstacles = new No17minPathSum();
        System.out.println(obstacles.minPathSum(grid));

    }

    /**
     * 解题思路：此题是典型的动态规划题目。
     * https://leetcode.cn/problems/minimum-path-sum/solution/zui-xiao-lu-jing-he-dong-tai-gui-hua-gui-fan-liu-c/
     * <p>
     * 状态定义：
     * <p>
     * 设 dp 为大小 m×n 矩阵，其中 dp[i][j]的值代表直到走到 (i,j)的最小路径和。
     * 转移方程：题目要求，只能向右或向下走，换句话说，当前单元格 (i,j) 只能从左方单元格 (i-1,j)或上方单元格 (i,j−1) 走到，因此只需要考虑矩阵左边界和上边界。
     * <p>
     * 走到当前单元格 (i,j)的最小路径和 == “从左方单元格 (i-1,j) 与 从上方单元格 (i,j-1) 走来的 两个最小路径和中较小的 ” ++ 当前单元格值 grid[i][j]。具体分为以下4种情况：
     * 1. 当左边和上边都不是矩阵边界时： 即当 i!=0 and j!=0 时，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]；
     * 2. 当只有左边是矩阵边界时： 只能从上面来，即当i=0, j!=0时， dp[i][j] = dp[i][j-1] + grid[i][j]；
     * 3. 当只有上边是矩阵边界时： 只能从左面来，即当i!=0, j=0时， dp[i][j] = dp[i-1][j] + grid[i][j] ；
     * 4. 当左边和上边都是矩阵边界时： 即当i=0, j=0时，其实就是起点， dp[i][j] = grid[i][j]；
     * 初始状态：dp 初始化即可，不需要修改初始 0 值。
     * 返回值：dp 矩阵右下角值，即走到终点的最小路径和。
     * <p>
     * 其实我们完全不需要建立 dp 矩阵浪费额外空间，直接遍历 grid[i][j] 修改即可。这是因为：grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j] ；
     * 原 grid 矩阵元素中被覆盖为dp元素后（都处于当前遍历点的左上方），不会再被使用到。
     * <p>
     * 复杂度分析：
     * 时间复杂度 O(M×N) ： 遍历整个grid矩阵元素。
     * 空间复杂度 O(1) ： 直接修改原矩阵，不使用额外空间。
     */
    public int minPathSum(int[][] grid) {
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                if (row == 0 && col == 0) {
                    continue;
                } else if (row == 0) {
                    // 无上侧,靠左移动
                    grid[row][col] = grid[row][col - 1] + grid[row][col];
                } else if (col == 0) {
                    // 无左侧，靠上移动
                    grid[row][col] = grid[row - 1][col] + grid[row][col];
                } else {
                    // 有上有左侧，取最小
                    grid[row][col] = Math.min(grid[row - 1][col], grid[row][col - 1]) + grid[row][col];
                }
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }

    private int[][] grid;

    /**
     * 1 3 1
     * 1 5 1
     * 4 2 1
     * 思路：(数据大的时候，会有大量重复检索)
     * 设 f(i) 是到i位置的最短距离。自底向上计算每个节点，则右下角开始: ===> 1
     * --- f(9) = min(f(6)+1, f(8)+2) ===> 1
     * --- f(6) = min(f(3)+1,f(5)+5)  ===> 1
     * --- f(3) = min(f(2)+3)         ===> 3 // 特殊无右侧
     * --- f(2) = min(f(1)+1)         ===> 1 // 特殊无上侧
     * --- f(1) = 1;
     */
    public int minPathSumMine(int[][] grid) {
        int row = grid.length - 1;
        int col = grid[0].length - 1;
        this.grid = grid;
        return getMinVal(row, col, 0);
    }


    private int getMinVal(int row, int col, int sum) {
        int val = grid[row][col];
        if (row == 0 && col == 0) {
            return sum + val;
        }
        System.out.println("get:" + row + "-" + col);
        sum += val;
        // 无上侧
        if (row == 0) {
            return getMinVal(row, col - 1, sum);
        }
        // 无左侧
        if (col == 0) {
            return getMinVal(row - 1, col, sum);
        }
        return Math.min(getMinVal(row - 1, col, sum), getMinVal(row, col - 1, sum));
    }
}
